home *** CD-ROM | disk | FTP | other *** search
/ BCI NET / BCI NET Dec 94.iso / archives / programming / c / gcc222-3.lha / const_class / list.ccp < prev    next >
Encoding:
Text File  |  1993-02-04  |  17.0 KB  |  955 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18.  
  19. #ifdef __GNUG__
  20. #pragma implementation
  21. #endif
  22. #include <builtin.h>
  23. #include "<T>.List.h"
  24.  
  25. <T>ListNode Nil<T>ListNode;
  26.  
  27. class init_Nil<T>ListNode
  28. {
  29. public:
  30.   init_Nil<T>ListNode() 
  31.   {
  32.     Nil<T>ListNode.tl = &Nil<T>ListNode;
  33.     Nil<T>ListNode.ref = -1;
  34.   }
  35. };
  36.  
  37. static init_Nil<T>ListNode Nil<T>ListNode_initializer;
  38.  
  39. <T>List& <T>List::operator = (<T>List& a)
  40. {
  41.   reference(a.P);
  42.   dereference(P);
  43.   P = a.P;
  44.   return *this;
  45. }
  46.  
  47. <T> <T>List::pop()
  48. {
  49.   <T> res = P->hd;
  50.   <T>ListNode* tail = P->tl;
  51.   reference(tail);
  52.   dereference(P);
  53.   P = tail;
  54.   return res;
  55. }
  56.  
  57. void <T>List::set_tail(<T>List& a)
  58. {
  59.   reference(a.P);
  60.   dereference(P->tl);
  61.   P->tl = a.P;
  62. }
  63.  
  64. <T>List <T>List::nth(int n)
  65. {
  66.   for (<T>ListNode* p = P; n-- > 0; p = p->tl);
  67.   reference(p);
  68.   return <T>List(p);
  69. }
  70.  
  71. <T>List <T>List::last()
  72. {
  73.   <T>ListNode* p = P;
  74.   if (p != &Nil<T>ListNode) while (p->tl != &Nil<T>ListNode) p = p->tl;
  75.   reference(p);
  76.   return <T>List(p);
  77. }
  78.  
  79. void <T>List::append(<T>List& l)
  80. {
  81.   <T>ListNode* p = P;
  82.   <T>ListNode* a = l.P;
  83.   reference(a);
  84.   if (p != &Nil<T>ListNode)
  85.   {
  86.     while (p->tl != &Nil<T>ListNode) p = p->tl;
  87.     p->tl = a;
  88.   }
  89.   else
  90.     P = a;
  91. }
  92.  
  93. int <T>List::length()
  94. {
  95.   int l = 0;
  96.   for (<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl) ++l;
  97.   return l;
  98. }
  99.  
  100. <T>&  <T>List::operator [] (int n)
  101. {
  102.   for (<T>ListNode* p = P; n-- > 0; p = p->tl);
  103.   return (p->hd);
  104. }
  105.  
  106. int operator == (<T>List& x, <T>List& y)
  107. {
  108.   <T>ListNode* a = x.P;
  109.   <T>ListNode* b = y.P;
  110.   
  111.   for (;;)
  112.   {
  113.     if (a == &Nil<T>ListNode)
  114.       return b == &Nil<T>ListNode;
  115.     else if (b == &Nil<T>ListNode)
  116.       return 0;
  117.     else if (a->hd == b->hd)
  118.     {
  119.       a = a->tl;
  120.       b = b->tl;
  121.     }
  122.     else
  123.       return 0;
  124.   }
  125. }
  126.  
  127.  
  128. void <T>List::apply(<T>Procedure f)
  129. {
  130.   for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
  131.     (*f)((p->hd));
  132. }
  133.  
  134. void <T>List::subst(<T&> old, <T&> repl)
  135. {
  136.   for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
  137.     if (p->hd == old)
  138.       p->hd = repl;
  139. }
  140.  
  141. <T> <T>List::reduce(<T>Combiner f, <T&> base)
  142. {
  143.   <T> r = base;
  144.   for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
  145.     r = (*f)(r, (p->hd));
  146.   return r;
  147. }
  148.  
  149. int <T>List::position(<T&> targ)
  150. {
  151.   int l = 0;
  152.   <T>ListNode* p = P;
  153.   for (;;)
  154.   {
  155.     if (p == &Nil<T>ListNode)
  156.       return -1;
  157.     else if (p->hd == targ)
  158.       return l;
  159.     else
  160.     {
  161.       ++l;
  162.       p = p->tl;
  163.     }
  164.   }
  165. }
  166.  
  167. int <T>List::contains(<T&> targ)
  168. {
  169.   <T>ListNode* p = P;
  170.   for (;;)
  171.   {
  172.     if (p == &Nil<T>ListNode)
  173.       return 0;
  174.     else if (p->hd == targ)
  175.       return 1;
  176.     else
  177.       p = p->tl;
  178.   }
  179. }
  180.  
  181. <T>List <T>List::find(<T&> targ)
  182. {
  183.   for (<T>ListNode* p = P; p != &Nil<T>ListNode && !(p->hd == targ); p=p->tl);
  184.   reference(p);
  185.   return <T>List(p);
  186. }
  187.  
  188. Pix <T>List::seek(<T&> targ)
  189. {
  190.   <T>ListNode* p = P; 
  191.   for (;;)
  192.   {
  193.     if (p == &Nil<T>ListNode)
  194.       return 0;
  195.     else if (p->hd == targ)
  196.       return Pix(p);
  197.     else
  198.       p = p->tl;
  199.   }
  200. }
  201.  
  202. int <T>List::owns(Pix i)
  203. {
  204.   <T>ListNode* p = P; 
  205.   for (;;)
  206.   {
  207.     if (p == &Nil<T>ListNode)
  208.       return 0;
  209.     else if (Pix(p) == i)
  210.       return 1;
  211.     else
  212.       p = p->tl;
  213.   }
  214. }
  215.  
  216. <T>List <T>List::find(<T>List& target)
  217. {
  218.   <T>ListNode* targ = target.P;
  219.   if (targ == &Nil<T>ListNode)
  220.     return <T>List(targ);
  221.  
  222.   <T>ListNode* p = P;
  223.   while (p != &Nil<T>ListNode)
  224.   {
  225.     if (p->hd == targ->hd)
  226.     {
  227.       <T>ListNode* a = p->tl;
  228.       <T>ListNode* t = targ->tl;
  229.       for(;;)
  230.       {
  231.         if (t == &Nil<T>ListNode)
  232.         {
  233.           reference(p);
  234.           return <T>List(p);
  235.         }
  236.         else if (a == &Nil<T>ListNode || !(a->hd == t->hd))
  237.           break;
  238.         else
  239.         {
  240.           a = a->tl;
  241.           t = t->tl;
  242.         }
  243.       }
  244.     }
  245.     p = p->tl;
  246.   }
  247.   return <T>List(&Nil<T>ListNode);
  248. }
  249.  
  250. int <T>List::contains(<T>List& target)
  251. {
  252.   <T>ListNode* targ = target.P;
  253.   if (targ == &Nil<T>ListNode)
  254.     return 0;
  255.  
  256.   <T>ListNode* p = P;
  257.   while (p != &Nil<T>ListNode)
  258.   {
  259.     if (p->hd == targ->hd)
  260.     {
  261.       <T>ListNode* a = p->tl;
  262.       <T>ListNode* t = targ->tl;
  263.       for(;;)
  264.       {
  265.         if (t == &Nil<T>ListNode)
  266.           return 1;
  267.         else if (a == &Nil<T>ListNode || !(a->hd == t->hd))
  268.           break;
  269.         else
  270.         {
  271.           a = a->tl;
  272.           t = t->tl;
  273.         }
  274.       }
  275.     }
  276.     p = p->tl;
  277.   }
  278.   return 0;
  279. }
  280.  
  281. void <T>List::del(<T&> targ)
  282. {
  283.   <T>ListNode* h = P;
  284.  
  285.   for (;;)
  286.   {
  287.     if (h == &Nil<T>ListNode)
  288.     {
  289.       P = h;
  290.       return;
  291.     }
  292.     else if (h->hd == targ)
  293.     {
  294.       <T>ListNode* nxt = h->tl;
  295.       reference(nxt);
  296.       dereference(h);
  297.       h = nxt;
  298.     }
  299.     else
  300.       break;
  301.   }
  302.  
  303.   <T>ListNode* trail = h;
  304.   <T>ListNode* p = h->tl;
  305.   while (p != &Nil<T>ListNode)
  306.   {
  307.     if (p->hd == targ)
  308.     {
  309.       <T>ListNode* nxt = p->tl;
  310.       reference(nxt);
  311.       dereference(p);
  312.       trail->tl = nxt;
  313.       p = nxt;
  314.     }
  315.     else
  316.     {
  317.       trail = p;
  318.       p = p->tl;
  319.     }
  320.   }
  321.   P = h;
  322. }
  323.  
  324. void <T>List::del(<T>Predicate f)
  325. {
  326.   <T>ListNode* h = P;
  327.   for (;;)
  328.   {
  329.     if (h == &Nil<T>ListNode)
  330.     {
  331.       P = h;
  332.       return;
  333.     }
  334.     else if ((*f)(h->hd))
  335.     {
  336.       <T>ListNode* nxt = h->tl;
  337.       reference(nxt);
  338.       dereference(h);
  339.       h = nxt;
  340.     }
  341.     else
  342.       break;
  343.   }
  344.  
  345.   <T>ListNode* trail = h;
  346.   <T>ListNode* p = h->tl;
  347.   while (p != &Nil<T>ListNode)
  348.   {
  349.     if ((*f)(p->hd))
  350.     {
  351.       <T>ListNode* nxt = p->tl;
  352.       reference(nxt);
  353.       dereference(p);
  354.       trail->tl = nxt;
  355.       p = nxt;
  356.     }
  357.     else
  358.     {
  359.       trail = p;
  360.       p = p->tl;
  361.     }
  362.   }
  363.   P = h;
  364. }
  365.  
  366. void <T>List::select(<T>Predicate f)
  367. {
  368.   <T>ListNode* h = P;
  369.   for (;;)
  370.   {
  371.     if (h == &Nil<T>ListNode)
  372.     {
  373.       P = h;
  374.       return;
  375.     }
  376.     else if (!(*f)(h->hd))
  377.     {
  378.       <T>ListNode* nxt = h->tl;
  379.       reference(nxt);
  380.       dereference(h);
  381.       h = nxt;
  382.     }
  383.     else
  384.       break;
  385.   }
  386.   <T>ListNode* trail = h;
  387.   <T>ListNode* p = h->tl;
  388.   while (p != &Nil<T>ListNode)
  389.   {
  390.     if (!(*f)(p->hd))
  391.     {
  392.       <T>ListNode* nxt = p->tl;
  393.       reference(nxt);
  394.       dereference(p);
  395.       trail->tl = nxt;
  396.       p = nxt;
  397.     }
  398.     else
  399.     {
  400.       trail = p;
  401.       p = p->tl;
  402.     }
  403.   }
  404.   P = h;
  405. }
  406.  
  407. void <T>List::reverse()
  408. {
  409.   <T>ListNode* l = &Nil<T>ListNode;
  410.   <T>ListNode* p = P; 
  411.   while (p != &Nil<T>ListNode)
  412.   {
  413.     <T>ListNode* nxt = p->tl;
  414.     p->tl = l;
  415.     l = p;
  416.     p = nxt;
  417.   }
  418.   P = l;
  419. }
  420.  
  421.  
  422. <T>List copy(<T>List& x)
  423. {
  424.   <T>ListNode* a = x.P;
  425.   if (a == &Nil<T>ListNode)
  426.     return <T>List(a);
  427.   else
  428.   {
  429.     <T>ListNode* h = new<T>ListNode(a->hd);
  430.     <T>ListNode* trail = h;
  431.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  432.     {
  433.       <T>ListNode* n = new<T>ListNode(a->hd);
  434.       trail->tl = n;
  435.       trail = n;
  436.     }
  437.     trail->tl = &Nil<T>ListNode;
  438.     return <T>List(h);
  439.   }
  440. }
  441.  
  442.  
  443. <T>List subst(<T&> old, <T&> repl, <T>List& x)
  444. {
  445.   <T>ListNode* a = x.P;
  446.   if (a == &Nil<T>ListNode)
  447.     return <T>List(a);
  448.   else
  449.   {
  450.     <T>ListNode* h = new <T>ListNode;
  451.     h->ref = 1;
  452.     if (a->hd == old)
  453.       h->hd = repl;
  454.     else
  455.       h->hd = a->hd;
  456.     <T>ListNode* trail = h;
  457.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  458.     {
  459.       <T>ListNode* n = new <T>ListNode;
  460.       n->ref = 1;
  461.       if (a->hd == old)
  462.         n->hd = repl;
  463.       else
  464.         n->hd = a->hd;
  465.       trail->tl = n;
  466.       trail = n;
  467.     }
  468.     trail->tl = &Nil<T>ListNode;
  469.     return <T>List(h);
  470.   }
  471. }
  472.  
  473. <T>List combine(<T>Combiner f, <T>List& x, <T>List& y)
  474. {
  475.   <T>ListNode* a = x.P;
  476.   <T>ListNode* b = y.P;
  477.   if (a == &Nil<T>ListNode || b == &Nil<T>ListNode)
  478.     return <T>List(&Nil<T>ListNode);
  479.   else
  480.   {
  481.     <T>ListNode* h = new<T>ListNode((*f)(a->hd, b->hd));
  482.     <T>ListNode* trail = h;
  483.     a = a->tl;
  484.     b = b->tl;
  485.     while (a != &Nil<T>ListNode && b != &Nil<T>ListNode)
  486.     {
  487.       <T>ListNode* n = new<T>ListNode((*f)(a->hd, b->hd));
  488.       trail->tl = n;
  489.       trail = n;
  490.       a = a->tl;
  491.       b = b->tl;
  492.     }
  493.     trail->tl = &Nil<T>ListNode;
  494.     return <T>List(h);
  495.   }
  496. }
  497.  
  498. <T>List reverse(<T>List& x)
  499. {
  500.   <T>ListNode* a = x.P;
  501.   if (a == &Nil<T>ListNode)
  502.     return <T>List(a);
  503.   else
  504.   {
  505.     <T>ListNode* l = new<T>ListNode(a->hd);
  506.     l->tl = &Nil<T>ListNode;
  507.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  508.     {
  509.       <T>ListNode* n = new<T>ListNode(a->hd);
  510.       n->tl = l;
  511.       l = n;
  512.     }
  513.     return <T>List(l);
  514.   }
  515. }
  516.  
  517. <T>List append(<T>List& x, <T>List& y)
  518. {
  519.   <T>ListNode* a = x.P;
  520.   <T>ListNode* b = y.P;
  521.   reference(b);
  522.   if (a != &Nil<T>ListNode)
  523.   {
  524.     <T>ListNode* h = new<T>ListNode(a->hd);
  525.     <T>ListNode* trail = h;
  526.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  527.     {
  528.       <T>ListNode* n = new<T>ListNode(a->hd);
  529.       trail->tl = n;
  530.       trail = n;
  531.     }
  532.     trail->tl = b;
  533.     return <T>List(h);
  534.   }
  535.   else
  536.     return <T>List(b);
  537. }
  538.  
  539. void <T>List::prepend(<T>List& y)
  540. {
  541.   <T>ListNode* b = y.P;
  542.   if (b != &Nil<T>ListNode)
  543.   {
  544.     <T>ListNode* h = new<T>ListNode(b->hd);
  545.     <T>ListNode* trail = h;
  546.     for(b = b->tl; b != &Nil<T>ListNode; b = b->tl)
  547.     {
  548.       <T>ListNode* n = new<T>ListNode(b->hd);
  549.       trail->tl = n;
  550.       trail = n;
  551.     }
  552.     trail->tl = P;
  553.     P = h;
  554.   }
  555. }
  556.  
  557. <T>List concat(<T>List& x, <T>List& y)
  558. {
  559.   <T>ListNode* a = x.P;
  560.   <T>ListNode* b = y.P;
  561.   if (a != &Nil<T>ListNode)
  562.   {
  563.     <T>ListNode* h = new<T>ListNode(a->hd);
  564.     <T>ListNode* trail = h;
  565.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  566.     {
  567.       <T>ListNode* n = new<T>ListNode(a->hd);
  568.       trail->tl = n;
  569.       trail = n;
  570.     };
  571.     for(;b != &Nil<T>ListNode; b = b->tl)
  572.     {
  573.       <T>ListNode* n = new<T>ListNode(b->hd);
  574.       trail->tl = n;
  575.       trail = n;
  576.     }
  577.     trail->tl = &Nil<T>ListNode;
  578.     return <T>List(h);
  579.   }
  580.   else if (b != &Nil<T>ListNode)
  581.   {
  582.     <T>ListNode* h = new<T>ListNode(b->hd);
  583.     <T>ListNode* trail = h;
  584.     for(b = b->tl; b != &Nil<T>ListNode; b = b->tl)
  585.     {
  586.       <T>ListNode* n = new<T>ListNode(b->hd);
  587.       trail->tl = n;
  588.       trail = n;
  589.     }
  590.     trail->tl = &Nil<T>ListNode;
  591.     return <T>List(h);
  592.   }
  593.   else
  594.     return <T>List(&Nil<T>ListNode);
  595. }
  596.  
  597. <T>List select(<T>Predicate f, <T>List& x)
  598. {
  599.   <T>ListNode* a = x.P;
  600.   <T>ListNode* h = &Nil<T>ListNode;
  601.   while (a != &Nil<T>ListNode)
  602.   {
  603.     if ((*f)(a->hd))
  604.     {
  605.       h = new<T>ListNode(a->hd);
  606.       <T>ListNode* trail = h;
  607.       for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  608.       {
  609.         if ((*f)(a->hd))
  610.         {
  611.           <T>ListNode* n = new<T>ListNode(a->hd);
  612.           trail->tl = n;
  613.           trail = n;
  614.         }
  615.       }
  616.       trail->tl = &Nil<T>ListNode;
  617.       break;
  618.     }
  619.     else
  620.       a = a->tl;
  621.   }
  622.   return <T>List(h);
  623. }
  624.  
  625. <T>List remove(<T>Predicate f, <T>List& x)
  626. {
  627.   <T>ListNode* a = x.P;
  628.   <T>ListNode* h = &Nil<T>ListNode;
  629.   while (a != &Nil<T>ListNode)
  630.   {
  631.     if (!(*f)(a->hd))
  632.     {
  633.       h = new<T>ListNode(a->hd);
  634.       <T>ListNode* trail = h;
  635.       for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  636.       {
  637.         if (!(*f)(a->hd))
  638.         {
  639.           <T>ListNode* n = new<T>ListNode(a->hd);
  640.           trail->tl = n;
  641.           trail = n;
  642.         }
  643.       }
  644.       trail->tl = &Nil<T>ListNode;
  645.       break;
  646.     }
  647.     else
  648.       a = a->tl;
  649.   }
  650.   return <T>List(h);
  651. }
  652.  
  653. <T>List remove(<T&> targ, <T>List& x)
  654. {
  655.   <T>ListNode* a = x.P;
  656.   <T>ListNode* h = &Nil<T>ListNode;
  657.   while (a != &Nil<T>ListNode)
  658.   {
  659.     if (!(a->hd == targ))
  660.     {
  661.       h = new<T>ListNode(a->hd);
  662.       <T>ListNode* trail = h;
  663.       for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  664.       {
  665.         if (!(a->hd == targ))
  666.         {
  667.           <T>ListNode* n = new<T>ListNode(a->hd);
  668.           trail->tl = n;
  669.           trail = n;
  670.         }
  671.       }
  672.       trail->tl = &Nil<T>ListNode;
  673.       break;
  674.     }
  675.     else
  676.       a = a->tl;
  677.   }
  678.   return <T>List(h);
  679. }
  680.  
  681. <T>List map(<T>Mapper f, <T>List& x)
  682. {
  683.   <T>ListNode* a = x.P;
  684.   <T>ListNode* h = &Nil<T>ListNode;
  685.   if (a != &Nil<T>ListNode)
  686.   {
  687.     h = new<T>ListNode((*f)(a->hd));
  688.     <T>ListNode* trail = h;
  689.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  690.     {
  691.       <T>ListNode* n = new<T>ListNode((*f)(a->hd));
  692.       trail->tl = n;
  693.       trail = n;
  694.     }
  695.     trail->tl = &Nil<T>ListNode;
  696.   }
  697.   return <T>List(h);
  698. }
  699.  
  700.  
  701. <T>List merge(<T>List& x, <T>List& y, <T>Comparator f)
  702. {
  703.   <T>ListNode* a = x.P;
  704.   <T>ListNode* b = y.P;
  705.  
  706.   if (a == &Nil<T>ListNode)
  707.   {
  708.     if (b == &Nil<T>ListNode)
  709.       return <T>List(&Nil<T>ListNode);
  710.     else
  711.       return copy(y);
  712.   }
  713.   else if (b == &Nil<T>ListNode)
  714.     return copy(x);
  715.  
  716.   <T>ListNode* h = new <T>ListNode;
  717.   h->ref = 1;
  718.   if ((*f)(a->hd, b->hd) <= 0)
  719.   {
  720.     h->hd = a->hd;
  721.     a = a->tl;
  722.   }
  723.   else
  724.   {
  725.     h->hd = b->hd;
  726.     b = b->tl;
  727.   }
  728.  
  729.   <T>ListNode* r = h;
  730.  
  731.   for(;;)
  732.   {
  733.     if (a == &Nil<T>ListNode)
  734.     {
  735.       while (b != &Nil<T>ListNode)
  736.       {
  737.         <T>ListNode* n = new <T>ListNode;
  738.         n->ref = 1;
  739.         n->hd = b->hd;
  740.         r->tl = n;
  741.         r = n;
  742.         b = b->tl;
  743.       }
  744.       r->tl = &Nil<T>ListNode;
  745.       return <T>List(h);
  746.     }
  747.     else if (b == &Nil<T>ListNode)
  748.     {
  749.       while (a != &Nil<T>ListNode)
  750.       {
  751.         <T>ListNode* n = new <T>ListNode;
  752.         n->ref = 1;
  753.         n->hd = a->hd;
  754.         r->tl = n;
  755.         r = n;
  756.         a = a->tl;
  757.       }
  758.       r->tl = &Nil<T>ListNode;
  759.       return <T>List(h);
  760.     }
  761.     else if ((*f)(a->hd, b->hd) <= 0)
  762.     {
  763.       <T>ListNode* n = new <T>ListNode;
  764.       n->ref = 1;
  765.       n->hd = a->hd;
  766.       r->tl = n;
  767.       r = n;
  768.       a = a->tl;
  769.     }
  770.     else
  771.     {
  772.       <T>ListNode* n = new <T>ListNode;
  773.       n->ref = 1;
  774.       n->hd = b->hd;
  775.       r->tl = n;
  776.       r = n;
  777.       b = b->tl;
  778.     }
  779.   }
  780. }
  781.  
  782. void <T>List::sort(<T>Comparator f)
  783. {
  784.   // strategy: place runs in queue, merge runs until done
  785.   // This is often very fast
  786.  
  787.   if (P == &Nil<T>ListNode || P->tl == &Nil<T>ListNode)
  788.     return;
  789.  
  790.   int qlen = 250;   // guess a good queue size, realloc if necessary
  791.  
  792.   <T>ListNode** queue = (<T>ListNode**)malloc(qlen * sizeof(<T>ListNode*));
  793.  
  794.   <T>ListNode* h = P;
  795.   <T>ListNode* a = h;
  796.   <T>ListNode* b = a->tl;
  797.   int qin = 0;
  798.  
  799.   while (b != &Nil<T>ListNode)
  800.   {
  801.     if ((*f)(a->hd, b->hd) > 0)
  802.     {
  803.       if (h == a)               // minor optimization: ensure runlen >= 2
  804.       {
  805.         h = b;
  806.         a->tl = b->tl;
  807.         b->tl = a;
  808.         b = a->tl;
  809.       }
  810.       else
  811.       {
  812.         if (qin >= qlen)
  813.         {
  814.           qlen *= 2;
  815.           queue = (<T>ListNode**)realloc(queue, qlen * sizeof(<T>ListNode*));
  816.         }
  817.         queue[qin++] = h;
  818.         a->tl = &Nil<T>ListNode;
  819.         h = a = b;
  820.         b = b->tl;
  821.       }
  822.     }
  823.     else
  824.     {
  825.       a = b;
  826.       b = b->tl;
  827.     }
  828.   }
  829.  
  830.   int count = qin;
  831.   queue[qin] = h;
  832.   if (++qin >= qlen) qin = 0;
  833.   int qout = 0;
  834.  
  835.   while (count-- > 0)
  836.   {
  837.     a = queue[qout];
  838.     if (++qout >= qlen) qout = 0;
  839.     b = queue[qout];
  840.     if (++qout >= qlen) qout = 0;
  841.  
  842.     if ((*f)(a->hd, b->hd) <= 0)
  843.     {
  844.       h = a;
  845.       a = a->tl;
  846.     }
  847.     else
  848.     {
  849.       h = b;
  850.       b = b->tl;
  851.     }
  852.     queue[qin] = h;
  853.     if (++qin >= qlen) qin = 0;
  854.  
  855.     for (;;)
  856.     {
  857.       if (a == &Nil<T>ListNode)
  858.       {
  859.         h->tl = b;
  860.         break;
  861.       }
  862.       else if (b == &Nil<T>ListNode)
  863.       {
  864.         h->tl = a;
  865.         break;
  866.       }
  867.       else if ((*f)(a->hd, b->hd) <= 0)
  868.       {
  869.         h->tl = a;
  870.         h = a;
  871.         a = a->tl;
  872.       }
  873.       else
  874.       {
  875.         h->tl = b;
  876.         h = b;
  877.         b = b->tl;
  878.       }
  879.     }
  880.   }
  881.   P = queue[qout];
  882.   free(queue);
  883. }
  884.     
  885. int <T>List::list_length()
  886. {
  887.   <T>ListNode* fast = P;
  888.   if (fast == &Nil<T>ListNode)
  889.     return 0;
  890.  
  891.   <T>ListNode* slow = fast->tl;
  892.   if (slow == &Nil<T>ListNode)
  893.     return 1;
  894.  
  895.   fast = slow->tl;
  896.   int n = 2;
  897.  
  898.   for (;;)
  899.   {
  900.     if (fast == &Nil<T>ListNode)
  901.       return n;
  902.     else if (fast->tl == &Nil<T>ListNode)
  903.       return n+1;
  904.     else if (fast == slow)
  905.       return -1;
  906.     else
  907.     {
  908.       n += 2;
  909.       fast = fast->tl->tl;
  910.       slow = slow->tl;
  911.     }
  912.   }
  913. }
  914.  
  915. void <T>List::error(const char* msg)
  916. {
  917.   (*lib_error_handler)("List", msg);
  918. }
  919.  
  920. int <T>List::OK()
  921. {
  922.   int v = P != 0;               // have a node
  923.   // check that all nodes OK, even if circular:
  924.  
  925.   <T>ListNode* fast = P;
  926.   if (fast != &Nil<T>ListNode)
  927.   {
  928.     v &= fast->ref != 0;
  929.     <T>ListNode* slow = fast->tl;
  930.     v &= slow->ref != 0;
  931.     if (v && slow != &Nil<T>ListNode)
  932.     {
  933.       fast = slow->tl;
  934.       v &= fast->ref != 0;
  935.       while (v)
  936.       {
  937.         if (fast == &Nil<T>ListNode)
  938.           break;
  939.         else if (fast->tl == &Nil<T>ListNode)
  940.           break;
  941.         else if (fast == slow)
  942.           break;
  943.         else
  944.         {
  945.           v &= fast->ref != 0 && slow->ref != 0;
  946.           fast = fast->tl->tl;
  947.           slow = slow->tl;
  948.         }
  949.       }
  950.     }
  951.   }
  952.   if (!v) error ("invariant failure");
  953.   return v;
  954. }
  955.